package schoolEmployeeTest;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @ClassName Huawei2
 * @description:
 * @author: 荣燊
 * @create: 2022-04-20 19:19
 **/
public class Huawei2 {
    public static ArrayList<Integer> resultList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 创建二叉树
        String s1 = scanner.nextLine();
        ArrayList<String> rootTreeArr = new ArrayList<>();
        for (int i=0; i<s1.length(); i++) {
            if (s1.charAt(i)-'0' >= 0 && s1.charAt(i)-'0' <= 9) {
                rootTreeArr.add(new String(s1.charAt(i)+""));
            }
        }
        TreeNode fatherTree = createTree(rootTreeArr);
        // 开始读取父树中的对应两个节点
        String s2 = scanner.nextLine();
        int[] nums = new int[2];
        int j=0;
        for (int i=0; i<s2.length(); i++) {
            if (s2.charAt(i)-'0' >= 0 && s2.charAt(i)-'0' <= 9) {
                nums[j] = s2.charAt(i); // ?
                j++;
            }
        }
        // 构件子树
        String s3 = scanner.nextLine();
        ArrayList<String> sonTreeArr = new ArrayList<>();
        for (int i=0; i<s3.length(); i++) {
            if (s3.charAt(i)-'0' >= 0 && s3.charAt(i)-'0' <= 9) {
                sonTreeArr.add(new String(s3.charAt(i)+""));
            }
        }
        TreeNode sonTree = createTree(sonTreeArr);
        // 开始比对替换
        dfs(fatherTree, nums[0], nums[1], sonTree);
        // 输出
        PreOrder(fatherTree);
        int k = 0;
        System.out.print("[");
        while (k < resultList.size()) {
            if (k < resultList.size()-1) {
                System.out.print(resultList.get(k)+",");
            } else {
                System.out.print(resultList.get(k));
            }
        }
        System.out.print("]");
    }

    //构造二叉树
    public static TreeNode createTree(ArrayList<String> nums) {
        List<TreeNode> list = new ArrayList<>();//将元素（int）保存到TreeNode中，直接对元素(Treenood(int))进行树创建的操作
        for (int i=0; i<nums.size(); i++) {
            if(!nums.get(i).equals("null")) {
                TreeNode node = new TreeNode(Integer.parseInt(nums.get(i)));
                list.add(node);
            }else{
                list.add(null);
            }
        }
        TreeNode root;
        for (int i=0; i<list.size()/2; i++) {//只用遍历到数组长度的一半
            root = list.get(i);//指向当前要进行操作（添加左右子节点）的节点
            if(root != null) {
                TreeNode left = list.get(i * 2 + 1);//添加左子节点
                if (left.val == 0) {
                    root.left = null;
                } else {
                    root.left = left;
                }
                if (i * 2 + 2 < list.size()) {//需要判断是否已经添加完毕
                    TreeNode right = list.get(i * 2 + 2);//添加右子节点
                    if (right.val == 0) {
                        root.right = null;
                    } else {
                        root.right = right;
                    }
                }
            }
        }
        return list.get(0);//返回根节点（因为二叉树是从List的第0个元素开始，即0处的元素为根节点）
    }

    // 比对替换
    public static void dfs(TreeNode root, int i, int j, TreeNode sonTree) {
        if (root == null) {
            return;
        }
        if (root.val == i) {
            if (root.left.val == j) {
                root.left = sonTree;
                return;
            }
            if (root.right.val == j) {
                root.right = sonTree;
                return;
            }
        }
        dfs(root.left, i, j, sonTree);
        dfs(root.right, i, j, sonTree);
    }

    // 前序遍历
    public static void PreOrder(TreeNode root) {
        if (root != null) {
            resultList.add(root.val);
            PreOrder(root.left);
            PreOrder(root.right);
        }
    }
}

// 树结构
class TreeNode {
    int val;
    public TreeNode(int x) {
        val = x;
    }
    TreeNode left;
    TreeNode right;
}
